Symmetric and asymmetric ciphering algorithms require a high quality random number source for key generation. Random numbers are also used for generating challenges in authentication protocols, to create padding bytes and blinding values for random masking.
A random bit generator (RBG) is a system whose output consists of fully unpredictable (i.e. statistically independent and unbiased) bits. Oscillator based random bit generators (RBG) employ a “slow” oscillator (Tslow) which samples a “fast” oscillator (Tfast). In order to generate high quality bits, the slow oscillator jitter must be sufficiently greater than the fast oscillator period Tfast.
Even if pseudo random number generators (PRNG) based on cryptographic secure deterministic algorithms can be employed for these purposes, a physical source of true randomness is needed for algorithm seeding. For this reason, a cryptographic token, like a chip-card, must also feature a true random number generator (RNG) among its peripheral devices.
The main feature of a high-quality randomness source is the unpredictability of the produced bit stream. An observer or even attacker must not be able to carry out any useful prediction about the true RNG output even if the design of the RNG is known.
A true RNG generates a random bit stream from a non-deterministic natural source like electronic noise or radioactive decay. Indeed, in an integrated implementation, electronic noise sources like thermal or shot noise are the only stochastic processes that can be exploited.
One technique for generating random bit streams is jittered oscillator sampling. A true RNG based on jittered oscillator sampling, basically, includes two free running oscillators and a sampling element like a single D-type flip-flop. An output signal from a slower of the two oscillators samples an output of the faster of the two oscillators, thus generating a bit stream. The resulting bit sequence derives from the oscillators mean frequency ratio and their cycle-to-cycle jitter. Properly chosen frequency ratios lead to bit streams that seem to be more random when statistical randomness tests are applied. Nevertheless, the output bit entropy is due to the oscillator's jitter being the only randomness source in such a system. If the sample signal of the fast oscillator features an unbalanced mean value, this in turn gives rise to an unbalanced mean value on the output bit stream or to an increase in its bit-to-bit correlation, according to the adopted sampling element. Moreover, periodic disturbances like a system clock can synchronize the sampling oscillator, thus dramatically reducing its jitter.
FIG. 1 shows a schematic view of a jittered oscillator sampling based RNG 100. RNG source 100 comprises a high-frequency oscillator 102, a low-frequency oscillator 104, a prescaler 106 and a sampler 108. The sampler 108 is a D-flip-flop. The high-frequency oscillator 102 generates a fast clock signal 110 which is a data input to the sampler 108. The low-frequency oscillator 104 generates a slow clock signal 112 which is prescaled by the prescaler 106. The prescaler 106 outputs a sample signal 114 which is an input to a clock input of the sampler 108. The sampler 108 samples the fast clock signal 110 on a rising edge of the sample signal 114 and outputs a random bit 116 which depends on a sampling state of the fast clock signal 110 while being sampled. Here, successive random bits 116 are an input to a digital post-processor 120 which outputs a random bit stream 122.
FIG. 2 shows characteristics of the fast clock signal 110, the slow clock signal 112 and the sample signal 114, as they are shown in FIG. 1. The fast clock signal 110 has a period Tfast and a duty cycle d. The slow clock signal 112 has a period Tslow. Edges of the slow clock signal 112 comprise a jitter. The sample signal 114 is generated from the slow clock signal 112 by prescaling the sample signal 112 by a factor defined in the prescaler. Here the slow clock signal 112 is prescaled by a factor of 4. As the sample signal 114 is generated from the slow clock signal 112, the edge of the sample signal 114 also comprises a jitter. A period of the sample signal 114 is TSAMPLE and a standard deviation of the jitter of the sample signal 114 is σ(TSAMPLE). Edges of the sample signal 114 and the fast clock signal 110 are not synchronized. Here the edge of the fast clock signal 110 occurs by a time period no later than the edge of the sample signal 114. Frequency beating of the two free running oscillators 102, 104 (shown in FIG. 1) generates a non-white noise signal. This is especially a problem in a standard-cell based RNG where typically the jitter has a low intensity. Moreover, an unbalanced random bit stream 122 is obtained if the duty cycle d of the fast clock signal 110 is unbalanced. A relative jitter with respect to the fast clock signal is helpful.
The entropy of the random values output by the random number generator is due to the relative jitter between the sample signal 114 and the sampled signal 112. However, the jitter-to-mean-period ratio is usually quite small so that the distribution of the random values is not as uniform as desired. One way to increase random stream quality is to increase the frequency of the fast clock signal 112. However, the frequency of the fast clock signal 112 cannot be increased indefinitely because of limits in implementing high-frequency oscillators. Another way to increase the random stream quality is to increase the jitter-to-mean-period ratio of the sample signal 114 by means of an amplified noise source inside the fast clock signal. This approach, however, results in an increase in chip area and power required for implementation.